package binary_tree.sort.LeetCode;

import java.util.*;

/*
* 查找和最小的K对数字
* */
public class Num373 {
    private class Pair implements Comparable<Pair>{
        int u;
        int v;
        public Pair(int u,int v) {
            //第一个元素
            this.u=u;
            //第二个元素
            this.v=v;
        }
        //优使用先级队列
        @Override
        public int compareTo(Pair o) {
            return (o.u+o.v)-(this.u+this.v);
        }
    }
    public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
        Queue<Pair> queue=new PriorityQueue<>();
        //最外层取值
        for(int i=0;i<Math.min(nums1.length,k);i++){
            //内层取值
            for(int j=0;j<Math.min(nums2.length,k);j++){
                if(queue.size()<k){
                    queue.offer(new Pair(nums1[i],nums2[j]));
                }else{
                    Pair pair=queue.peek();
                    if((nums1[i]+nums2[j])<(pair.u+ pair.v)){
                        queue.poll();
                        queue.offer(new Pair(nums1[i],nums2[j]));
                    }
                }
            }
        }
        //此时队列中储存了前K个最小的pair对象
        List<List<Integer>> ret=new ArrayList<>();
        //边界条件是k>queen.size()
        for(int i=0;i<k&&!(queue.isEmpty());i++){
           List<Integer> temp=new ArrayList<>();
           Pair pair=queue.poll();
           temp.add(pair.u);
           temp.add(pair.v);
           ret.add(temp);

        }
        return ret;
    }
}
//        PriorityQueue<List<Integer>> maxHeap=new PriorityQueue<>(new Comparator<List<Integer>>() {
//            @Override
//            public int compare(List<Integer> o1, List<Integer> o2) {
//                return ((o2.get(0)+o2.get(1))-(o1.get(0)+o1.get(1)));
//            }
//        });
//        for(int i=0;i<Math.min(nums1.length,k);i++){
//            for(int j=0;j<Math.min(nums2.length, k);j++){
//                if(maxHeap.size()<k){
//                    List<Integer> list=new ArrayList<>();
//                    list.add(nums1[i]);
//                    list.add(nums2[j]);
//                    maxHeap.add(list);
//                }else {
//                    int top=maxHeap.peek().get(0)+maxHeap.peek().get(1);
//                    if(top>nums1[i]+nums2[j]){
//                        maxHeap.poll();
//                        List<Integer> list=new ArrayList<>();
//                        list.add(nums1[i]);
//                        list.add(nums2[j]);
//                        maxHeap.add(list);
//                    }
//
//                }
//            }
//        }
//        List<List<Integer>> res=new ArrayList<>();
//        for(int i=0;i<k&&!maxHeap.isEmpty();i++){
//            res.add(maxHeap.poll());
//        }
//        return res;

